#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <cstdlib>
#include <cstdint>
#include <ctime>
#include <stack>
#include <string>

using namespace std;
//在stack内部维护递增序列，递增序列方便遍历所有组合情况，得到最大值
//一旦遇到更小的值，欲破环递增序列，就需要把前面的最大值计算好，再压入新值
//栈中第一个元素应该是-1，目的是标记数组的起始位置
class Solution {
public:
    vector<vector<int>> test;
    int largestRectangleArea(vector<int>& heights) {
        stack<int> sta;
        int max = 0;
        int i;
        sta.push(-1);
        for (i = 0; i < heights.size(); i++){
            while(sta.size() > 1 && heights[i] < heights[sta.top()]){
                int popValue = heights[sta.top()];
                sta.pop();
                int erea = popValue * (i - sta.top() - 1);
                if (erea > max){
                    max = erea;
                }
            }
            sta.push(i);
        }

        while(sta.size() > 1){
            int popValue = heights[sta.top()];
            sta.pop();
            int erea = popValue * (i - sta.top() - 1);
            if (erea > max){
                max = erea;
            }
        }
        return max;
    }
};

int main()
{
    Solution su;
    su.test.push_back(vector<int>({2,1,5,6,2,3}));
    su.test.push_back(vector<int>({2,1,2}));
    su.test.push_back(vector<int>({5,4,1,2}));

    for (int i = 0; i < su.test.size(); i++){
        int result = su.largestRectangleArea(su.test[i]);
        cout << result << endl;
    }
    return 0;
}
